\documentclass[12pt]{article}
\usepackage{calc,fancyhdr}
\usepackage[hmargin=.5in,vmargin=.75in,
            footskip=.25in,headsep=.5in-\headheight]{geometry}

% Template solution to Exercise 2.

% Common formatting macros for CSC165.
\usepackage{amsmath,amssymb}
\input{macros-165}

% Page layout: stretch text to fill up page.
\flushbottom

% Headings.
\pagestyle{fancy}
\let\headrule\empty
\let\footrule\empty
\lhead{CSC\,165\,H1S}
\chead{Homework Exercise \#\,2}
\rhead{Winter 2014}

\begin{document}

\begin{large}
  \noindent
  Name : Robert Staskiewicz \hfill CDF login name: c3staski\\
  Partner : Ekam Shahi \hfill CDF login name: c3shahie\\[0.5cm]
\end{large}

\medskip

\noindent
\rule{\textwidth}{.5pt}

\subsection*{Topic: Quantification and Implication}

\medskip

\begin{enumerate}
 
       
    % place solution to question 1 below

    \item
    \begin{itemize}
        \item Expressing the English statements as precise quantified statements.
        \begin{enumerate}
            \item $\exists\ x \in F, R(x) $
            \item $\forall\ x \in F, \neg R(x)$
            \item $\forall\ x \in F, R(x)$
            \item $\exists\ x \in F, \neg R(x)$
        \end{enumerate}
        \item Considering the elements examined in the loop:
        \begin{enumerate}
            \item We have an existential quantification, which only needs one example to be proven true. Therefore, the loop can stop when a first year student’s number is found in both F and R.
            \item We have a universal quantification. To validate the statement, there should be no first year student number in R, which requires the loop to iterate over both elements of F and R to verify that no element exists in both F and R.
            \item We have a universal quantification. The loop must iterate through every element of F and R to show that every first year student’s number is in F and R.
            \item We have an existential quantification. The statement only needs one example to be proven true. Therefore, the loop can stop iterating over F, as soon as it finds one first year student number in both F and R. 
        \end{enumerate}
    \end{itemize}
    
    % place solution to question 2 below

    \item 
    \begin{enumerate}
        \item $\forall\ x \in \N, O(x) \implies P(x)$
        \item Proof by  Counterexample: $
        \\
        9 \in \N, O
        \\
        9 = 3*3\\
        (3*3) \notin P \implies 9 \notin P$        
        \\
        Therefore, (S1) is false. 
        \item 
            \begin{enumerate}
                \item All nonprime numbers are even natural numbers.
                \item $\exists x \in \N, \neg P(x) \implies \neg O(x) $
            \end{enumerate}
        \item 
            \begin{enumerate}
                \item All prime numbers are odd natural numbers.
                \item $\forall x \in \N, P(x) \implies O(x)$
            \end{enumerate}
    \end{enumerate}

    
    % place solution to question 3 below

    \item 
    C is a set of all computers.\\ N is a predicate that operates on the set C and is defined by N(x): Computer x is on a network.\\P is a predicate that operates on the set C and is defined by P(x): Computer x has an IP address.\\
            S is a predicate that operates on the set C and is defined by S(x): Computer x can share files.
    \begin{enumerate}
    	
        \item If a computer is on a network, then it has an IP address.
        \item
        $\forall x \in C, N(x) \implies P(x) $ 
        \item
        $\forall x \in C, P(x) \implies S(x)$
        \item We can conclude from (S2), which we know to be true, that every computer on a network has an IP address.\\ 
        $ \forall x \in C, N(x) \implies P(x) $\\
        Therefore, our computer has an IP address.\\
        Also, based on (S3),
        $ P(x) \implies  S(x)$ \\
        Therefore, if x is a computer and x is on a network, then x has an IP address and x can share files. 
        \item If computer x does not have an IP address, then we can conclude that it is not on a network by (S2).\\ In logical notation: $\forall x \in C, \neg N(x) \in \neg P(x) $\\ We can also conclude that computer x cannot share files, since an IP address is required to share files by (S3).\\ In logical notation: $\forall x \in C, \neg P(x) \implies \neg S(x)$
        
        % We can conclude that x is not on a network, because based on (S2), every computer on a network has an ip address.\\
        %$ x \notin N \implies x \notin P $\\
        %Also, based on (S3), we can conclude that x cannot share files, because it does not have an IP address and a computer can only share files with an ip address.\\
        %$ x \notin P \implies x \notin S $\\
    \end{enumerate}

\end{enumerate}

\medskip

\noindent
\rule{\textwidth}{.5pt}

\end{document}
